# 85/100 动态规划-最长递增子序列
# leetcode第300题: https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/26
from leetcode import test


def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    if n < 2:
        return n

    dp = [1] * n
    res = 1
    for i in range(1, n):
        for j in range(i - 1, -1, -1):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        res = max(dp[i], res)

    return res


def lengthOfLIS_opt(nums: list[int]) -> int:
    """一种新的方法
    重点在于利用二分查找法, 将元素放置在一个非严格的递增的队列中, 而队列的长度就是最长子序列的长度.

    执行示例:
    nums = [111, 222, 0, 1, 2, 3, 4]

    初始化 res_list = [111]。
    遍历 222：添加 222，res_list = [111, 222]。
    遍历 0：替换 111，res_list = [0, 222]。此处就不是一个严格的递增序列, 因为0在222后面. 但是递增序列的长度相同的.
    遍历 1：扩展，res_list = [0, 1]。
    遍历 2：替换 5，res_list = [2, 3]。
    以此类推: 得到结果为 [0, 1, 2, 3, 4]

    """
    n = len(nums)
    if n < 2:
        return n

    res_list = [nums[0]]  # 非严格的最长的递增子序列
    for num in nums:
        if num > res_list[-1]:
            res_list.append(num)
        else:
            # 使用二分查找法查找下一个递增的元素
            l, r = 0, len(res_list) - 1
            loc = r
            while l <= r:
                mid = (l + r) // 2
                loc = mid
                if res_list[mid] < num:
                    l = mid + 1
                    loc = l
                else:
                    r = mid - 1
            res_list[loc] = num
    return len(res_list)


if __name__ == '__main__':
    # 验证
    inp = [{"nums": [10, 9, 2, 5, 3, 7, 101, 18]}, {"nums": [0, 1, 0, 3, 2, 3]}, {"nums": [7, 7, 7, 7, 7, 7, 7]},
           {"nums": [111, 222, 0, 1, 2, 3, 4]}, ]
    out = [4, 4, 1, 5]

    test.test_function(lengthOfLIS, inp, out)
    test.test_function(lengthOfLIS_opt, inp, out)
